package com.zyj.test.month1.day15;

/**
 * @author Yijia Zhang
 * @create 2024-06-04 21:05
 */
public class code0029 {
    //快速乘
    public int divideV2(int dividend, int divisor) {
        final int minInt = Integer.MIN_VALUE;
        if (dividend == minInt && divisor == -1) {
            return minInt;
        }
        if (divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            return -dividend;
        }

        boolean reverse = false;
        if (dividend > 0) {
            dividend = -dividend;
            reverse = !reverse;
        }
        if (divisor > 0) {
            divisor = -divisor;
            reverse = !reverse;
        }
        //二分查找
        int l = 0, r = Integer.MAX_VALUE - 1;
        while (l < r) {
            int mid = l + (r - l + 1 >> 1);
            int tmp = quickMultiply(divisor, mid);
            if (tmp >= dividend) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int res = l;

        return reverse ? -res : res;


    }
    //a < 0, b > 0
    public int quickMultiply(int a, int b) {
        if (a == 0 || b == 0) {
            return 0;
        }
        if (b == 1) {
            return a;
        }

        int res = 0;
        while (a <= -b) {
            int tmpR = -b;
            int k = 1;
            while (tmpR + tmpR >= a && tmpR + tmpR < 0) {
                tmpR = tmpR + tmpR;
                k = k + k;
            }
            a -= tmpR;
            res += k;
        }
        return res;
    }

}
